public class MySingleList {
        static class ListNode {
            public int val;
            public ListNode next;

            public ListNode(int val) {

                this.val = val;
            }
        }

        public ListNode head;

        public void display() {
            ListNode cur = head;
            while (cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
        }

        public int size() {
            ListNode cur = head;
            int count = 0;
            while (cur != null) {
                count++;
                cur = cur.next;
            }
            return count;
        }

        public boolean contains(int key) {
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

        public void addFirst(int data) {
            ListNode cur = new ListNode(data);
            cur.next = head;
            head = cur;
        }

        public void addLast(int data) {
            ListNode cur = head;
            if (cur == null) {
                head = new ListNode(data);
                return;
            }
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new ListNode(data);
        }

        public void addIndex(int data, int index) {
            ListNode cur = head;
            if (index < 0 || index > size()) {
                throw new IllegalPositionException("位置不合法");
            }
            if (index == 0) {
                addFirst(data);
                return;
            }
            if (index == size()) {
                addLast(data);
                return;
            }
            ListNode A = new ListNode(data);
            for (int i = 0; i < index - 1; i++) {
                cur = cur.next;
            }
            A.next = cur.next;
            cur.next = A;

        }


        public void remove(int key) {
            if (head == null) {
                System.out.println("null key to delete");
                return;
            }

            if (head.val == key) {
                head = head.next;
                return;
            }

            ListNode cur = head;
            ListNode del;
            while (cur.next != null) {
                del = cur.next;
                if (del.val == key) {
                    cur.next = del.next;
                    return;
                }
                cur = cur.next;
            }
        }



// 易错！！！！！
   public void removeAllKey(int key) {
    // 处理空链表情况
    if (head == null) {
        System.out.println("链表为空，无法移除节点");
        return;
    }
    
    // 处理头节点等于key的情况
    while (head != null && head.val == key) {
        head = head.next;
    }
    
    // 再次检查链表是否为空
    if (head == null) {
        return;
    }
    
    ListNode prev = head;
    ListNode curr = head.next;
    
    // 遍历链表
    while (curr != null) {
        if (curr.val == key) {
            
            prev.next = curr.next;
            
        } else {
            
            prev = curr;
        }
        curr = curr.next; 
    }
}






        public void clear() {
            this.head = null;
        }
        public void reverse() {
            if (head == null) {
                return;
            }
            if (head.next == null) {
                return;
            }
            ListNode cur = head.next;

            head.next = null;
            while (cur != null) {
                ListNode nextCur = cur.next;
                cur.next = head;
                head = cur;
                cur = nextCur;

            }

        }
        public ListNode findKthToTail (int k) {
            if (k <= 0 || head == null) {
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            for (int i = 0; i < k-1; i++) {
                if (fast.next == null) {
                    return null;
                }
                fast = fast.next;
            }
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;

            }
            return slow;
        }
        public ListNode mergeTwoList(ListNode list1,ListNode list2) {
            ListNode headA = list1;
            ListNode headB = list2;
            ListNode newHead = new ListNode(0);
            ListNode temHead = newHead;
            while (headA != null && headB != null) {
                if (headA.val > headB.val) {
                    temHead.next = headB;
                    temHead = temHead.next;
                    headB = headB.next;
                } else {
                    temHead.next = headA;
                    temHead = temHead.next;
                    headA = headB.next;
                }
            }
            if (headA == null) {
                temHead.next = headB;
            }
            if (headB == null) {
                temHead.next = headA;
            }
            return newHead.next;
        }
    public ListNode partition(ListNode list,int x) {
        ListNode smallHead = null;
        ListNode bigHead = null;
        ListNode smallEnd = null;
        ListNode bigEnd =null;
        ListNode cur = list;
        while (cur != null) {
            if (cur.val < x) {
                if (smallHead == null){
                    smallHead = cur;
                    smallEnd = cur;
                }else {
                    smallEnd.next = cur;
                    smallEnd = smallEnd.next;
                }
            } else {
                if (bigHead == null) {
                    bigHead = cur;
                    bigEnd = cur;
                } else {
                    bigEnd.next = cur;
                    bigEnd = bigEnd.next;
                }
            }
            cur = cur.next;
        }
        if (smallHead == null) {
            return bigHead;
        }
        smallEnd.next = bigHead;
        bigEnd.next = null;
        return smallHead;
    }
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        while (slow != head) {
            if (head.next == slow) {
                if (head.val == slow.val) {
                    return true;
                }
                else{
                    return false;
                }
            }
            if (head.val != slow.val) {
                return false;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }
    public boolean hasCycle(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenthA = 0;
        int lenthB = 0;
        ListNode cur = headA;
        ListNode cur2 = headB;
        if (headA == null || headB == null) {
            return null;
        }

        while (cur != null) {
            lenthA++;
            cur = cur.next;
        }
        while (cur2 != null) {
            lenthB++;
            cur2 = cur2.next;
        }
        //让长的先走
        int len = lenthA - lenthB;
        if (len < 0) {
            len = -len;
            for (int i = 0; i < len; i++) {
                headB = headB.next;
            }
        } else {
            for (int i = 0; i < len; i++) {
                headA = headA.next;
            }
        }
        //求节点
        while (headA != null && headB != null) {
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }

}
